package 排序算法.交换排序;

//快速排序
//基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，
//将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,
//然后再用同样的方法递归地排序划分的两部分。
//快速排序的时间复杂度为O(nlogn)。
//当n较大时使用快排比较好，当序列基本有序时用快排反而不好。
public class Quick_Sort {

    public static void main(String[] args) {
        int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8};
        sort(a);
    }

    private static void sort(int[] a){
        System.out.println("排序之前：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
        //快速排序
        sort_quick(a,0,a.length-1);
        System.out.println();
        System.out.println("排序之后：");
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+" ");
        }
    }

    private static void quick(int[] a) {
        if(a.length>0){
            quickSort(a,0,a.length-1);
        }
    }
    //选择一个基准划分
    private static void quickSort(int[] a, int low, int high) {
        if(low<high) { //如果不加这个判断递归会无法退出导致堆栈溢出异常
            int middle = getMiddle(a, low, high);
            //递归将剩下的分组进行再快排,知道参数low=high
            quickSort(a, low, middle - 1);
            quickSort(a, middle + 1, high);
        }
    }

    private static int getMiddle(int[] a, int low, int high) {
        int temp=a[low]; //以第一个值为基准
        while (low<high){
            while (low<high&&a[high]>=temp){//找到小于基准的值
                high--;
            }
            //存在两种情况，一种是找到了且low<high，则将high赋值到low的位置，第二种是没找到，说明这是升序的不用排序。
            //这样赋值则原来的high处数据可以随时被替换
            a[low]=a[high];
            while (low<high&&a[low]<temp){
                low++;
            }
            a[high]=a[low];
        }
        a[low]=temp; //此时的low和high相等
        return low; //目的是以a[low]为界限分割两个区域（大小）
    }

    //方法二：
    static void sort_quick(int[] a, int low, int high){
        if (low>=high){
            return;
        }

        int left=low;
        int right=high;
        int temp=a[low];
        while (low<high){
            while (low<high&&a[high]>=temp){//找到小于基准的值
                high--;
            }
            //存在两种情况，一种是找到了且low<high，则将high赋值到low的位置，第二种是没找到，说明这是升序的不用排序。
            //这样赋值则原来的high处数据可以随时被替换
            a[low]=a[high];
            while (low<high&&a[low]<=temp){
                low++;
            }
            a[high]=a[low];
        }
        a[low]=temp; //此时的low和high相等
        sort_quick(a,left,low-1);
        sort_quick(a,low+1,right);
    }
}
